//问题 B: 【数据结构2-10】单向有序链表按值插入（DS版本）
//时间限制: 1 Sec  内存限制: 128 MB
//提交: 386  解决: 134
//[提交][状态][论坛]
//题目描述
//原由链表结点的数据是按照从小到大排序的，输入一个新的数据，插入到链表中，使它仍然有序
//
//输入
//第一行输入一组正整数（ 其他以从小到大的序列给出）-1结束，创建链表
//
//第二行输入要插入的整数
//
//输出
//插入后有序的序列
//样例输入
//1 3 4 5 7 9 -1
//6
//样例输出
//1 3 4 5 6 7 9

#include"stdlib.h"
#include<iostream>
using namespace std;

typedef int datatype;
#define MAXLEN 100

typedef struct linknode {
	datatype data;
	struct linknode *next;
} LinkNode,*LinkList;

//创建链表
LinkList CreatLinkList() {
	LinkList L = new LinkNode,p=L;
	datatype x;
	cin>>x;
	while(x!=-1) {
		LinkNode *q = new LinkNode;
		q->data=x;
		p->next=q;
		p=q;

		cin>>x;
	}
	p->next=NULL;
	return L;
}
//在链表中搜索插入的位置
int SearchLinkList(LinkList L,datatype x) {
	LinkNode *p=L;
	int pos=0;
	while(p->next!=NULL&&x>p->next->data) {
		p=p->next;
		pos++;
	}
	return pos;

}
//在指定位置插入新节点
void InsLinkList(LinkList L,int pos,datatype x) {
	LinkNode *p=L;
	for(int i=0; i<pos; i++) {
		p=p->next;
	}
	LinkNode *q = new LinkNode;
	q->data=x;
	q->next = p->next;
	p->next=q;
}

void ShowLinkList(LinkList L) {
	LinkNode *p=L->next;
	while(p!=NULL) {
		cout<<p->data<<" ";
		p=p->next;
	}
	cout << endl;
}
int main() {
	LinkList L;
	datatype x;
	int pos=0;

	L = CreatLinkList();
	cin>>x;
	pos = SearchLinkList(L, x);
	InsLinkList(L,pos,x);
	ShowLinkList(L);
	return 0;
} 